#ifndef RA_H_
#define RA_H_

#include "tools.hpp"
#include <cstddef>
#include <cstdint>
#include <type_traits>
#include <winbase.h>
#include <winerror.h>
#include <winscard.h>
#include <xutility>


namespace lxj
{
// 随机快速排序
template<class Iter,
         class Val,
         std::enable_if_t<std::is_same_v<Val, std::decay_t<decltype(*Iter())>>, int> = 0>
inline size_t partition1(Iter first, Iter last, Val val)
{
    auto swap = [](Val& a, Val& b) {
        Val temp = a;
        a        = b;
        b        = temp;
    };
    auto a = first, xi = first;
    for (auto i = first; i <= last; i++) {
        if (*i <= val) {
            swap(*i, *a);
            xi = *a == val ? a : xi;
            a++;
        }
    }
    swap(*xi, *(a - 1));
    return a - 1 - first;
}

template<class Iter>
inline void quick_sort1(Iter first, Iter last)
{
    if (first >= last) return;

    std::_Adl_verify_range(first, last);
    static_assert(std::_Is_random_iter_v<Iter>, "需要随机迭代器或指针");

    auto ufirst = std::_Get_unwrapped(first);
    auto ulast  = std::_Get_unwrapped(last);

    size_t size  = ulast - ufirst;
    size_t index = lxj::Random<size_t>::instance()(0, size);
    size_t mid   = partition1(ufirst, ulast, *(first + index));
    quick_sort1(ufirst, ufirst + mid - 1);
    quick_sort1(ufirst + mid + 1, last);
}

template<class Iter,
         class Val,
         std::enable_if_t<std::is_same_v<Val, std::decay_t<decltype(*Iter())>>, int> = 0>
inline auto partition2(Iter first, Iter last, Val val)
{
    struct pos {
        int l = 0;
        int r = 0;
    };
    auto swap = [](Val& a, Val& b) {
        Val temp = a;
        a        = b;
        b        = temp;
    };

    pos p{.l = 0, .r = 0};
    for (Iter i = first; i <= last - p.r;) {
        if (*i == val) {
            i++;
        }
        else if (*i < val) {
            swap(*(first + p.l), *i);
            p.l++;
            i++;
        }
        else {
            swap(*(last - p.r), *i);
            p.r++;
        }
    }
    return p;
}

template<class Iter>
inline void quick_sort2(Iter first, Iter last)
{
    if (first >= last) return;

    std::_Adl_verify_range(first, last);
    static_assert(std::_Is_random_iter_v<Iter>, "需要随机迭代器或指针");

    auto ufirst = std::_Get_unwrapped(first);
    auto ulast  = std::_Get_unwrapped(last);

    size_t size  = ulast - ufirst;
    size_t index = lxj::Random<size_t>::instance()(0, size);
    auto [l, r]  = partition2(ufirst, ulast, *(ufirst + index));
    quick_sort2(ufirst, ufirst + l - 1);
    quick_sort2(last - r + 1, last);
}

template<class Number, std::enable_if_t<std::is_arithmetic_v<Number>, int> = 0>
inline void partition(Number* a, size_t size, int l, int r, int& first, int& last, Number rand)
{
    auto swap = [](Number& a, Number& b) {
        Number temp = a;
        a           = b;
        b           = temp;
    };
    first = l;
    last  = r;
    int i = l;
    while (i <= last) {
        if (*(a + i) == rand) {
            i++;
        }
        else if (*(a + i) < rand) {
            swap(*(a + first), *(a + i));
            first++;
            i++;
        }
        else {
            swap(*(a + last), *(a + i));
            last--;
        }
    }
}

template<class Number, std::enable_if_t<std::is_arithmetic_v<Number>, int> = 0>
inline Number randomized_select(Number* a, size_t size, int i)
{
    Number ans   = INT32_MIN;
    int    first = 0, last = 0;
    auto&  rand = lxj::Random<int>::instance();
    for (int l = 0, r = size - 1; l <= r;) {
        partition(a, size, l, r, first, last, *(a + rand(l, r)));
        if (i < first) {
            r = first - 1;
        }
        else if (i > last) {
            l = last + 1;
        }
        else {
            ans = *(a + i);
            break;
        }
    }
    return ans;
}

// 返回无序数组中第K大的数字
template<class Number, std::enable_if_t<std::is_arithmetic_v<Number>, int> = 0>
inline Number findKthLargest(Number* a, size_t size, int k)
{
    return randomized_select(a, size, size - k);
}


}   // namespace lxj


#endif